/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/* serialized format:
 * BYTE expo
 * 		the exponent of the serialized tree
 *
 * DATA
 * 		data is binary code.the following codes are defined:
 * 		0: empty voxel
 * 		10: filled voxel
 * 		11: sub-voxels (with serialization of that voxel following)
 *
 * 		serialization starts with data is VecType::childCount codes for the top level nodes of the tree
 * 		trailing zeroes are ignored
 */


#pragma once

#include "NTree.h"
#include <iostream>

int
addBits(unsigned int in, unsigned int nInBits,
		unsigned int& out, unsigned int& overflow, bool& bOut,
		unsigned int bits, unsigned int nBits)
{
	unsigned int iBitCount = nInBits + nBits;
	static const unsigned int max = sizeof(int)*8;

	if(iBitCount>max)
	{
		bOut=true;

		//write overflow
		int nOverflowBits=iBitCount-max;
		int nNonOverflowBits=max-nInBits;//nBits-nOverflowBits;
		overflow = bits & ((1<<(nOverflowBits))-1);

		//re-assign what still fits into the word
		bits=bits>>(nOverflowBits);
		nBits=nNonOverflowBits;

		iBitCount-=max;
	}
	out = (in<<nBits) | bits;

	return iBitCount;
}

template<class VecType, class T>
void
serializeTree(NTree<VecType, T>& tree, std::ostream& out)
{
	//first byte is tree expo
	unsigned char cSize=tree.getSize();
	out.write((char*)&cSize, 1);
	//then goes serialized data
	typename NTree<VecType, T>::Node** pStack=new typename NTree<VecType, T>::Node*[(1+tree.getSize()) * VecType::childCount];

	for(int iNode=VecType::childCount-1; iNode>=0; iNode--)
		pStack[iNode]=&tree.getRoot(iNode);

	int iStack=VecType::childCount-1;
	unsigned int bits=0;
	int iBit=0;

	while(iStack>=0)
	{
		unsigned int uiBits, nBits;
		//directly pops the current stack element
		switch(pStack[iStack]->getType())
		{
		case Nil:
			uiBits = 0;
			nBits = 1;
			iStack--;
			break;
		case Solid:
			uiBits = 2;
			nBits = 2;
			iStack--;
			break;
		default: // Both
			uiBits = 3;
			nBits = 2;
			typename NTree<VecType, T>::Node* currNode=pStack[iStack];
			//iterate last stack element
			//overwrite current stack element
			for(int iNode=VecType::childCount-1; iNode>=0; iNode--)
				pStack[iStack+iNode]=&currNode->getSubNode(iNode);
			iStack+=VecType::childCount-1;
			break;
		}
		bool bOutput=false;
		unsigned int uiOverflow;

		iBit=addBits(bits, iBit, bits, uiOverflow, bOutput, uiBits, nBits);

		if(bOutput)
		{
			for(int iByte=sizeof(unsigned int)-1; iByte >=0 ; iByte--)
			{
				unsigned char c=(bits>>(iByte<<3))&0xFF;
				out.write((char*) &c, sizeof(unsigned char));
			}
			bits=uiOverflow;
		}
	}
	//flush buffer
	if(iBit)
	{
		//pad bits from the right
		int nPadBits=(sizeof(unsigned int)<<3)-iBit;
		bool unused;
		unsigned int uiUnused;
		addBits(bits, iBit, bits, uiUnused, unused, 0, nPadBits);

		for(int iByte=sizeof(unsigned int)-1; iByte >=0 ; iByte--)
		{
			unsigned char c=(bits>>(iByte<<3))&0xFF;
			out.write((char*) &c, sizeof(unsigned char));
		}
	}
	delete pStack;
}

template<class VecType>
class DeserializeCon
{
public:
	DeserializeCon(std::istream& input) : in(input), iBit(0)
	{
		unsigned char cSize;
		in.read((char*)&cSize, 1);
		size=cSize;
		cInput=0;
		in.read((char*)&cInput, 1);
	}
	const int getSize() const {return size;}

	const VoxelType fn(const Box<VecType>& box)
	{
		VoxelType output;
		//try to deserialize the input
		//read first bit
		if(cInput&(1<<(7-iBit)))
		{//first bit is set, need to read another bit
			//check if this is an overflow
			iBit++;
			if(iBit>7)
			{
				cInput=0;
				in.read((char*)&cInput, 1);
				iBit=0;
			}

			if(cInput&(1<<(7-iBit)))
				output = Both;
			else
				output=Solid;
		}
		else
		//this is an empty voxel
			output=Nil;

		iBit++;
		if(iBit>7)
		{
			cInput=0;
			in.read((char*)&cInput, 1);
			iBit=0;
		}
		return output;
	}
private:
	std::istream& in;
	unsigned char cInput;
	int iBit;
	int size;
};
